<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<div id="cnblogs_post_body" class="blogpost-body cnblogs-markdown">
    <h1 id="线性同余方程">线性同余方程</h1>
    <h3 id="定义">定义</h3>
    <p>线性同余方程就是形如 <span class="math inline">\(ax\equiv b\pmod m\)</span> 其中 <span class="math inline">\(a,b,m\)</span>
        是给定的整数。</p>
    <h3 id="解法">解法</h3>
    <p>由同余的性质可知 <span class="math inline">\(m\mid ax-b\)</span> 即 <span class="math inline">\(ax-b=km\)</span>
        其中 <span class="math inline">\(k\in \mathbb{Z}\)</span>。</p>
    <p>如果我们设 <span class="math inline">\(k=-y\)</span> 的话，就有 <span class="math inline">\(ax+my=b\)</span>，发现了吗？其实这就是
        <a href="https://www.cnblogs.com/rp-plus-plus/p/18923876" target="_blank">Bézout 定理</a>。</p>
    <p>由<strong>Bézout 定理</strong>我们可以得到，这个同余方程有解当且仅当 <span
            class="math inline">\(\gcd(a,m)\mid b\)</span>。</p>
    <p>我们考虑在有解的情况下使用扩展欧几里得算法先求解出 <span class="math inline">\(ax+my=\gcd(a,m)\)</span> 的一组特解
        <span class="math inline">\(\left\{\begin{matrix}x=x_0 \\y=y_0\end{matrix}\right.\)</span>，然后呢，我们就可以得到
        <span class="math inline">\(x=\frac{x_0\times b}{\gcd(a,m)}\)</span> 就是原方程的一组解。</p>
    <h4 id="关于扩展欧几里得算法的说明">关于扩展欧几里得算法的说明</h4>
    <h5 id="内容">内容</h5>
    <p>我们考虑不定方程 <span class="math inline">\(ax+by=\gcd(a,b)\)</span> 的一组特解，我们可以采用递归的方法来求解，实际上这也就是扩展欧几里得算法：
    </p>
    <ol>
        <li>显然当 <span class="math inline">\(b=0\)</span> 时，有 <span class="math inline">\(\left\{\begin{matrix}x=1\\y=0\end{matrix}\right.\)</span>
            满足条件。
        </li>
        <li>当 <span class="math inline">\(b\ne 0\)</span> 时，我们根据欧几里得算法有 <span class="math inline">\(\gcd(a,b)=\gcd(b,a\bmod b)\)</span>
            于是，我们就有 <span class="math inline">\((a\bmod b)y+bx=\gcd(b,a\bmod b)\)</span> 又由于 <span
                    class="math inline">\((a\bmod b)y+bx=\left(a-b\times\lfloor\frac{a}{b}\rfloor\right)\times y+bx\)</span>
            将 <span class="math inline">\(\operatorname{RHS}\)</span> 展开，合并同类项后有 <span class="math inline">\((a\bmod b)y+bx=ay+b\times \left(x-\lfloor\frac{a}{b}\rfloor y\right)\)</span>
            于是，我们令 <span class="math inline">\(x_0=y,y_0=x-\lfloor \frac{a}{b}\rfloor y\)</span> 就有 <span
                    class="math inline">\(ax_0+by_0=\gcd(a,b)\)</span>。
        </li>
    </ol>
    <h5 id="代码实现">代码实现</h5>
    <p>根据上述内容，我们可以打出扩展欧几里得算法的代码：</p>
    <pre><code class="language-cpp">int exgcd(int a,int b,int&amp;x,int&amp;y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int z=x;
	x=y;
	y=z-z*y;
	return d;
}
</code></pre>
    <h5 id="功能介绍">功能介绍</h5>
    <p>以上函数的返回值为 <span class="math inline">\(\gcd(a,b)\)</span>，注意到参数 <span
            class="math inline">\(x,y\)</span> 均在前面加上了取地址符，表示在函数中可以改变 <code>x</code> 与
        <code>y</code> 的值，而函数运行完成后 <code>x</code> 与 <code>y</code> 所保存的值就是 <span class="math inline">\(ax+by=\gcd(a,b)\)</span>
        的一组特解。</p>
    <h3 id="一道模板题">一道模板题</h3>
    <p><a href="https://www.luogu.com.cn/problem/P1082" target="_blank" rel="noopener nofollow">洛谷 P1082</a>：</p>
    <p>这道题目就是模板题，方程可以写成 <span class="math inline">\(ax+by=1\)</span> 的形式，于是我们使用扩展欧几里得算法，可以求出特解
        <span class="math inline">\(x_0\)</span> 然后 <span class="math inline">\(x_0\bmod b\)</span> 就是原方程的最小正整数解了。
    </p>
    <pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
#define int long long
using namespace std;
int a,b;
int exgcd(int a,int b,int&amp;x,int&amp;y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int z=x;
	x=y;
	y=z-(a/b)*y;
	return d;
}
signed main(){
	cin&gt;&gt;a&gt;&gt;b;
	int x,y;
	exgcd(a,b,x,y);
	cout&lt;&lt;(x%b+b)%b;
	return 0;
}
</code></pre>
    <h1 id="线性同余方程组">线性同余方程组</h1>
    <p>作者太懒了，这里先讲解更加宽泛的扩展中国剩余定理吧，等以后再讲解特殊的中国剩余定理，顺便宣传一下博客：<a
            href="https://www.cnblogs.com/rp-plus-plus/p/19174819" target="_blank">link</a>。</p>
    <h3 id="问题简述">问题简述</h3>
    <p>给定一个 <span class="math inline">\(k\)</span> 个方程的线性同余方程组：</p>
    <p></p>
    <div class="math display">\[\left\{\begin{matrix}
        x\equiv a_1\pmod {m_1}\\x\equiv a_2\pmod {m_2}
        \\\vdots
        \\x\equiv a_k\pmod {m_k}

        \end{matrix}\right.\]
    </div>
    <p></p>
    <p>其中 <span class="math inline">\(m_1,m_2,\dots,m_k\)</span> 不一定两两互质。</p>
    <h3 id="解题方法">解题方法</h3>
    <p>我们的大致解题思路为将 <span class="math inline">\(2\)</span> 个方程合并为一个新的方程，以此类推，最终我们会得到一个
        <span class="math inline">\(x\equiv y\pmod z\)</span> 的一个方程，易见上面的方程组的最小正整数解就是 <span
                class="math inline">\(y\)</span>。</p>
    <p>接下来我们来解决合并方程的问题，我们考虑如下两个方程：</p>
    <p></p>
    <div class="math display">\[\left\{\begin{matrix}
        x\equiv a_1\pmod {m_1}\\x\equiv a_2\pmod {m_2}


        \end{matrix}\right.\]
    </div>
    <p></p>
    <p>我们根据第一个式子可以写出 <span class="math inline">\(x\)</span> 的通解 <span class="math inline">\(x=a_1+m_1\times k\)</span>
        其中 <span class="math inline">\(k\)</span> 为任意整数，我们将这个通解带入第二个式子就可以得到 <span
                class="math inline">\(a_1+m_1\times k\equiv a_2\pmod {m_2}\)</span> 我们移一下项就可以得到 <span
                class="math inline">\(m_1\times k\equiv a_2-a_1\pmod {m_2}\)</span>，这就是上面的方程组合并后的结果。</p>
    <p>而这个方程有解的充要条件是 <span class="math inline">\(\gcd(m_1,m_2)\mid a_2-a_1\)</span>，这个其实就是裴蜀定理，这里不再概述。
    </p>
    <p>我们继续讲，我们得到这个充要条件后我们可以判断这个方程是否有解，如果有解我们就继续进行接下来的操作。</p>
    <p>我们设 <span class="math inline">\(d=\gcd(m_1,m_2)\)</span>，然后将我们合并的方程变换一下就是：</p>
    <p></p>
    <div class="math display">\[\frac{m_1\times k}{d}\equiv \frac{a_2-a_1}{d}\pmod {\frac{m_2}{d}}
        \]
    </div>
    <p></p>
    <p>然后，我们设 <span class="math inline">\(m_1'=\frac{m_1}{d},c=\frac{a_2-a_1}{d},m_2'=\frac{m_2}{d}\)</span>
        于是我们就有：</p>
    <p></p>
    <div class="math display">\[m_1'\times k\equiv c\pmod {m_2'}
        \]
    </div>
    <p></p>
    <p>注意到此时 <span class="math inline">\(m_1',m_2'\)</span> 互质，所以 <span class="math inline">\(m_1'\)</span> 在模
        <span class="math inline">\(m_2'\)</span> 的意义下存在乘法逆元，我们可以使用扩展欧几里得算法来求出逆元，即求出整数
        <span class="math inline">\(inv\)</span> 使得 <span
                class="math inline">\(m_1'\times inv\equiv 1\pmod {m_2'}\)</span>，所以我们继续将这个方程变换就变成了：
    </p>
    <p></p>
    <div class="math display">\[k\equiv c\times inv\pmod {m_2'}
        \]
    </div>
    <p></p>
    <p>如果我们记 <span class="math inline">\(k_0=c\times inv\)</span> 则 <span class="math inline">\(k\)</span> 的通解为
        <span class="math inline">\(k_0+m_2'\times t\)</span> 其中 <span class="math inline">\(t\)</span> 为任意整数。
    </p>
    <p>然后我们将这个 <span class="math inline">\(k\)</span> 带回一开始的式子就可以得出：</p>
    <p></p>
    <div class="math display">\[\begin{aligned}
        x&amp;=a_1+m_1\times(k_0+m_2'\times t)\\
        &amp;=(a_1+m_1\times k_0)+(m_1\times m_2')\times t\\
        &amp;=(a_1+m_1\times k_0)+\frac{m_1\times m_2}{d}\times t\\
        &amp;=(a_1+m_1\times k_0)+\mathrm{lcm}(m_1,m_2)\times t\end{aligned}\]
    </div>
    <p></p>
    <p>我们设 <span class="math inline">\(x_0=a_1+m_1\times k_0,L=\mathrm{lcm}(m_1,m_2)\)</span> 所以我们就愉快地得出了：
    </p>
    <p></p>
    <div class="math display">\[\left\{\begin{matrix}
        x\equiv a_1\pmod {m_1}\\x\equiv a_2\pmod {m_2}


        \end{matrix}\right.\Longleftrightarrow x\equiv x_0\pmod L\]
    </div>
    <p></p>
    <p>于是，我们完成了合并方程的使命！</p>
    <p>最后其实就是一个递推的过程我们一次合并前 <span class="math inline">\(2\)</span> 个方程，最后就能得到答案！</p>
    <h3 id="代码实现-1">代码实现</h3>
    <pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
#define LL __int128
#define R register
using namespace std;
namespace fastIO{char *p1,*p2,buf[100000];
	#define nc() (p1==p2&amp;&amp;(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
	inline void read(LL&amp;n){LL x=0,f=1;char ch=nc();while(ch&lt;48||ch&gt;57){if(ch=='-'){f=-1;}ch=nc();}while(ch&gt;=48&amp;&amp;ch&lt;=57){x=(x&lt;&lt;3)+(x&lt;&lt;1)+(ch^48),ch=nc();}n=x*f;}inline void read(string&amp;s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&amp;&amp;ch!='\n'){s+=ch,ch=nc();}}inline void read(char&amp;ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}inline void write(LL x){if(x&lt;0){putchar('-'),x=-x;}if(x&gt;9){write(x/10);}putchar(x%10+'0');return;}inline void write(const string&amp;s){for(R LL i=0;i&lt;(int)s.size();i++){putchar(s[i]);}}inline void write(const char&amp;c){putchar(c);}
}using namespace fastIO;
inline LL mul(LL a,LL b,const LL&amp;mod){
    a=(a%mod+mod)%mod;
    b=(b%mod+mod)%mod;
    LL res=0;
    while(b){
        if(b&amp;1)res=(res+a)%mod;
        a=(a+a)%mod;
        b&gt;&gt;=1;
    }
    return res;
}
void exgcd(LL a,LL b,LL&amp;x,LL&amp;y){
    if(b==0){
        x=1;
        y=0;
    }
	else{
        exgcd(b,a%b,y,x);
        y-=x*(a/b);
    }
}
LL inv_mod(LL a,LL m){
    LL x,y;
    exgcd(a,m,x,y);
    return (x%m+m)%m;
}
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}
LL n,a[100005],b[100005];
signed main(){
    read(n);
    for(int i=0;i&lt;n;i++){
    	read(a[i]);
    	read(b[i]);
    }
    LL a0=a[0];
    LL b0=(b[0]%a0+a0)%a0;
    for(int i=1;i&lt;n;i++){
        LL ai=a[i];
        LL bi=(b[i]%ai+ai)%ai;
        LL d=gcd(a0,ai);
        LL dif=bi-b0;
        LL a0_=a0/d;
        LL ai_=ai/d;
        LL dif_=dif/d;
        LL c=(dif_%ai_+ai_)%ai_;
        LL inv=inv_mod(a0_,ai_);
        LL t0=mul(inv,c,ai_);
        LL a0__=(a0/d)*ai;
        LL mod__=a0__;
        LL p=mul(a0,t0,mod__);
        LL b0__=(b0+p)%mod__;
        a0=mod__;
        b0=b0__;
    }
	write(b0);
    return 0;
}
</code></pre>
    <h1 id="一些例题">一些例题</h1>
    <p>如果有不会的可以回复作者！</p>
    <ul>
        <li><a href="https://www.luogu.com.cn/problem/P5656" target="_blank" rel="noopener nofollow">洛谷 P5655</a>。
        </li>
        <li><a href="https://www.luogu.com.cn/problem/P2480" target="_blank" rel="noopener nofollow">洛谷 P2480</a>。
        </li>
    </ul>

</div>
</body>
</html>
